package reviewAlgorithms.search;

public class FindCircleNum {
    public static void main(String[] args) {
        int[][] M = {{1,1,0},{1,1,0},{0,0,1}};
        System.out.println(findCircleNum(M));
    }
    public static int findCircleNum(int[][] M) {

        if (M == null || M.length < 1){
            return 0;
        }
        int rowNum = M.length;
        int columnNum = M[0].length;
        int count = 0;
        int[] state = new int[rowNum];
        if (rowNum != columnNum){
            return 0;
        }
        for (int i = 0; i < columnNum; i++) {
            if (state[i] == 0){
                getCircle(i,state,M);
                count ++;
            }
        }
        return count;
    }

    private static void getCircle(int i, int[] state, int[][] m) {
        state[i] = 1;
        int[] rows = m[i];
        for (int j = 0; j < rows.length; j++) {
            if (i != j && state[j] == 0 && rows[j] == 1){
                getCircle(j,state,m);
            }
        }
    }
}
